#include <iostream>
#include <queue>
#include <deque>
#include <vector>
#include <string>
using namespace std;

template<typename T>
class Queue {
private:
    deque<T> items;
    
public:
    // 入队
    void enqueue(T item) {
        items.push_back(item);
        cout << "入队: " << item << endl;
    }
    
    // 出队
    T dequeue() {
        if (isEmpty()) {
            throw runtime_error("队列为空");
        }
        T item = items.front();
        items.pop_front();
        cout << "出队: " << item << endl;
        return item;
    }
    
    // 查看队头元素
    T front() {
        if (isEmpty()) {
            throw runtime_error("队列为空");
        }
        return items.front();
    }
    
    // 判断队列是否为空
    bool isEmpty() {
        return items.empty();
    }
    
    // 获取队列的大小
    int size() {
        return items.size();
    }
    
    // 打印队列内容
    void print() {
        cout << "队列内容: ";
        for (int i = 0; i < items.size(); i++) {
            cout << items[i] << " ";
        }
        cout << endl;
    }
    
    // 清空队列
    void clear() {
        items.clear();
        cout << "队列已清空" << endl;
    }
};

// 循环队列实现
template<typename T>
class CircularQueue {
private:
    vector<T> queue;
    int capacity;
    int front;
    int rear;
    int size;
    
public:
    CircularQueue(int cap) : capacity(cap), front(0), rear(0), size(0) {
        queue.resize(capacity);
    }
    
    // 入队
    void enqueue(T item) {
        if (isFull()) {
            throw overflow_error("队列已满");
        }
        queue[rear] = item;
        rear = (rear + 1) % capacity;
        size++;
        cout << "入队: " << item << endl;
    }
    
    // 出队
    T dequeue() {
        if (isEmpty()) {
            throw runtime_error("队列为空");
        }
        T item = queue[front];
        queue[front] = T(); // 清空元素
        front = (front + 1) % capacity;
        size--;
        cout << "出队: " << item << endl;
        return item;
    }
    
    // 判断队列是否为空
    bool isEmpty() {
        return size == 0;
    }
    
    // 判断队列是否已满
    bool isFull() {
        return size == capacity;
    }
    
    // 获取队列大小
    int getSize() {
        return size;
    }
    
    // 打印队列内容
    void print() {
        cout << "循环队列内容: ";
        for (int i = 0; i < size; i++) {
            int idx = (front + i) % capacity;
            cout << queue[idx] << " ";
        }
        cout << endl;
    }
};

// 任务调度器
class TaskScheduler {
private:
    Queue<string> taskQueue;
    
public:
    void submitTask(const string& task) {
        taskQueue.enqueue(task);
        cout << "任务已提交: " << task << endl;
    }
    
    string executeNextTask() {
        if (!taskQueue.isEmpty()) {
            string task = taskQueue.dequeue();
            cout << "正在执行: " << task << endl;
            return task;
        } else {
            cout << "没有待执行的任务" << endl;
            return "";
        }
    }
    
    int getTaskCount() {
        return taskQueue.size();
    }
};

// 广度优先搜索
vector<string> bfs(const map<string, vector<string>>& graph, const string& start) {
    vector<string> result;
    set<string> visited;
    queue<string> q;
    
    q.push(start);
    visited.insert(start);
    
    while (!q.empty()) {
        string vertex = q.front();
        q.pop();
        result.push_back(vertex);
        
        auto it = graph.find(vertex);
        if (it != graph.end()) {
            for (const string& neighbor : it->second) {
                if (visited.find(neighbor) == visited.end()) {
                    visited.insert(neighbor);
                    q.push(neighbor);
                }
            }
        }
    }
    
    return result;
}

void testBasicOperations() {
    cout << "=== 测试队列的基本操作 ===" << endl;
    
    Queue<int> queue;
    
    // 测试空队列
    cout << "队列是否为空: " << (queue.isEmpty() ? "是" : "否") << endl;
    cout << "队列的大小: " << queue.size() << endl;
    
    // 入队操作
    cout << "\n--- 入队操作 ---" << endl;
    queue.enqueue(1);
    queue.enqueue(2);
    queue.enqueue(3);
    queue.enqueue(4);
    queue.enqueue(5);
    
    queue.print();
    cout << "队列的大小: " << queue.size() << endl;
    cout << "队头元素: " << queue.front() << endl;
    
    // 出队操作
    cout << "\n--- 出队操作 ---" << endl;
    while (!queue.isEmpty()) {
        try {
            queue.dequeue();
            queue.print();
        } catch (const exception& e) {
            cout << "错误: " << e.what() << endl;
        }
    }
    
    cout << "队列是否为空: " << (queue.isEmpty() ? "是" : "否") << endl;
}

void testCircularQueue() {
    cout << "\n=== 测试循环队列 ===" << endl;
    
    CircularQueue<int> cq(3);
    
    // 入队操作
    cq.enqueue(1);
    cq.enqueue(2);
    cq.enqueue(3);
    cq.print();
    
    // 出队一个元素
    cq.dequeue();
    cq.print();
    
    // 继续入队
    cq.enqueue(4);
    cq.print();
    
    // 全部出队
    while (!cq.isEmpty()) {
        cq.dequeue();
        cq.print();
    }
}

void testTaskScheduler() {
    cout << "\n=== 测试任务调度器 ===" << endl;
    
    TaskScheduler scheduler;
    scheduler.submitTask("任务A");
    scheduler.submitTask("任务B");
    scheduler.submitTask("任务C");
    
    cout << "待执行任务数: " << scheduler.getTaskCount() << endl;
    
    scheduler.executeNextTask();  // 执行任务A
    scheduler.executeNextTask();  // 执行任务B
    scheduler.executeNextTask();  // 执行任务C
    scheduler.executeNextTask();  // 没有任务
}

void testBFS() {
    cout << "\n=== 测试广度优先搜索 ===" << endl;
    
    // 示例图
    map<string, vector<string>> graph = {
        {"A", {"B", "C"}},
        {"B", {"A", "D", "E"}},
        {"C", {"A", "F"}},
        {"D", {"B"}},
        {"E", {"B", "F"}},
        {"F", {"C", "E"}}
    };
    
    vector<string> result = bfs(graph, "A");
    
    cout << "BFS遍历结果: ";
    for (const string& vertex : result) {
        cout << vertex << " ";
    }
    cout << endl;
}

int main() {
    cout << "队列（Queue）数据结构演示程序" << endl;
    cout << "==================================================" << endl;
    
    try {
        // 运行所有测试
        testBasicOperations();
        testCircularQueue();
        testTaskScheduler();
        testBFS();
        
        cout << "\n==================================================" << endl;
        cout << "所有测试完成！" << endl;
        cout << "==================================================" << endl;
    } catch (const exception& e) {
        cout << "程序执行出错: " << e.what() << endl;
    }
    
    return 0;
}
